Non-patent literature 1 discloses an art of providing a computation result while concealing an input value. FIG. 1 is a block diagram showing a configuration of a secure computing system based on the art disclosed in Non-patent literature 1. Referring to FIG. 1, the secure computing system has a secure computing apparatus 81A and a secure computing apparatus 81B.
The secure computing apparatus 81A retains a logic circuit function f(x, y) and a bit string mA, which is to be substituted for x of the logic circuit function. The secure computing apparatus 81B retains the logic circuit function f(x, y) and a bit string mB, which is to be substituted for y of the logic circuit function.
The secure computing apparatuses 81A and 81B communicate with each other, and either or both of the secure computing apparatuses 81A and 81B obtain the computation result f(mA, mB) of the logic circuit function f(x, y). However, the secure computing apparatus 81A obtains no data from which the bit string mB can be readily reconstructed, and the secure computing apparatus 81B obtains no data from which the bit string mA can be readily reconstructed.
Note that the logic circuit function f(x, y) can be implemented as a combination of one or more logic gates g. A logic gate g performs a predetermined logic computation on one or two input bits and outputs one bit representing the computation result. The example of the logic gate may be the AND gate or the OR gate. Input and output sequences of each logic gate g are referred to as a wire. A wire on the input side is referred to as an input wire, and a wire on the output side is referred to as an output wire.
The method disclosed in Non-patent literature 1 will be summarized below. As an example, a procedure by which the secure computing apparatus 81A obtains the computation result f(mA, mB) will be described.
[Step C-1]
The secure computing apparatus 81B, which retains the logic circuit function f(x, y) and the bit string mB to be substituted for y, conceals the logic circuit function f(x, y) by concealing a truth table for each logic gate constituting the logic circuit function f(x, y).
The following is a truth table for a logic gate. In the case of the AND gate, g(0, 0)=g(0, 1)=g(1, 0)=0, and g(1, 1)=1.
Input wire:Output wire0, 0:g(0, 0)0, 1:g(0, 1)1, 0:g(1, 0)1, 1:g(1, 1)
To conceal a logic gate, the secure computing apparatus 81B associates each input wire and each output wire with a pair of a fixed-length random number, which is associated with the value of the wire, and a random bit, which is associated with the value of the wire. Then, the truth table is reconstructed using the associated pairs of a fixed-length random number and a random bit to conceal the truth table. However, this is not sufficient because even a person who does not know the association between the value of each wire and the pair of a fixed-length random number and a random bit can estimate the logic gate from the pair of a fixed-length random number and a random bit associated with the output wire. Thus, a pseudo-random function is applied to enhance the concealing. In this way, the logic gate can be concealed. Then, the remaining logic gates of the logic circuit function f(x, mB) can be concealed in the same way, thereby concealing the logic circuit function f (x, mB).
More specifically, the secure computing apparatus 81B performs the following steps (a) to (d) to conceal the logic circuit function f(x, mB).
(a) The secure computing apparatus 81B generates fixed-length random numbersWi0,Wi1 for each wire i for the logic circuit function f(x, mB) and associates the random numbers with 0 and 1, respectively.
(b) Then, the secure computing apparatus 81B generates a random bit ciε{0, 1}. The random bit ci is used as a randomized label.
(c) Then, the secure computing apparatus 81B associates(Wi0,ci,Wi1, ci)with the wire i. In this expression, c=1−c. Note that <α, β> means that α is associated with β.
(d) Then, for a logic gate g that receives input wires i and j and provides an output wire k, the secure computing apparatus 81B generates four pieces of labeled dataci,cj:(Wkg(0,0),g(0,0)⊕ck)⊕FWi0(cj)⊕FWj0(ci),ci, cj:(Wkg(0,1),g(0,1)⊕ck)⊕FWi0( cj)⊕FWj1(ci), ci,cj:(Wkg(1,0),g(1,0)⊕ck)⊕FWi1(cj)⊕FWj0( ci), ci, cj:(Wkg(1,1),g(1,1)⊕ck)⊕FWi1( cj)⊕FWj1( ci),and arranges the four pieces of labeled data in a random order to generate data Tg. In this expression, the left side of the colon represents a label, the right side of the colon represents data, and FW(x) represents a function that receives x and W and outputs a fixed-length random number that is uniquely determined for a pair of x and W (a pseudo-random function).α⊕βrepresents an exclusive OR of α and β.(α,β)⊕γrepresents an exclusive OR of a bit concatenated value α|β and γ, where α|β represents the bit concatenated value of α and β.
The random bit ck of the data Tg associated with the last-stage gate g of the logic circuit function f is set at 0.
The data Tg described above is generated for each gate of the logic circuit function f(x, mB), and a set T of the generated data Tg is transmitted to the secure computing apparatus 81A as concealing data for the logic circuit function f(x, mB).
[Step C1-2]
The secure computing apparatus 81A, which retains the bit string mA to be substituted for x, performs a 1-out-of-2 oblivious transfer protocol with the secure computing apparatus 81B. As a result, the secure computing apparatus 81A obtains dataWib,b⊕ci,associated with an input wire that is a bit bε{0, 1} of the bit string mA.
[Step C1-3]
Then, using the data Tg received from the secure computing apparatus 81B andWib,b⊕ci,the secure computing apparatus 81A computes the output wireWk{circumflex over (b)},{circumflex over (b)}⊕ckof the last logic gate g of the logic circuit function f.
[Step C1-4]
Furthermore, fromWk{circumflex over (b)},{circumflex over (b)}⊕ck,the secure computing apparatus 81A obtains a bit{circumflex over (b)}of the computation result f(mA, mB).
[Details of Step C1-3]
In step C1-3 in the procedure described above, when the data Tg associated with the gate that receives the input wires i and j and provides the output wire k andWib,b⊕ci,Wjd,d⊕cj(dε{0,1})  (1)are given, the secure computing apparatus 81A first retrieves data(Wkg(b,d),g(b,d)⊕ck)⊕FWib)(d⊕cj)⊕FWjd(b⊕ci)  (2)associated with the label(b⊕ci,d⊕cj)from the data Tg. In addition, the secure computing apparatus 81A computesFWib,(d⊕cj)⊕FWid(b⊕ci).  (3)The secure computing apparatus 81A performs an exclusive-OR operation of the formulas (2) and (3), thereby obtaining data(Wkg(b,d),g(b,d)⊕ck)  (4)associated with the output wire. Then, for example, the secure computing apparatus 81A uses the data associated with the output wire as data for an input wire of another logic gate and performs the same processing for the remaining logic gates to eventually obtain the output wire of the last-stage logic gate g of the logic circuit function f.
[Details of Step C1-4]
Since the random bit ck of the data Tg associated with the last-stage logic gate g of the logic circuit function f is set at 0,(Wk{circumflex over (b)},{circumflex over (b)}⊕ck=Wk{circumflex over (b)},{circumflex over (b)}⊕0=Wk{circumflex over (b)},{circumflex over (b)}.Therefore, the secure computing apparatus 81A can obtain{circumflex over (b)}in step C1-4.
As described above, according to the method described in Non-patent literature 1, the secure computing apparatuses 81A and 81B have to perform the 1-out-of-2 oblivious transfer protocol in the second step. The 1-out-of-2 oblivious transfer protocol is characterized in that, when the secure computing apparatus 81B retains data d0 and d1, and the secure computing apparatus 81A retains a bit b, the secure computing apparatus 81A can obtain db but cannot obtaind b,and the secure computing apparatus 81B cannot obtain the bit b. By using the protocol, leakage of the bit b of the bit string mA from the secure computing apparatus 81A to the secure computing apparatus 81B can be prevented, and at the same time, leakage of information about the logic circuit function f(x, mB) concealed in the data Tg to the secure computing apparatus 81A can be prevented. For detailed information on the protocol, see Non-patent literature 2.
Non-patent literature 3 discloses another art of providing a computation result while concealing an input value. FIG. 2 is a block diagram showing a configuration of a secure computing system based on the art disclosed in Non-patent literature 3. Referring to FIG. 2, the secure computing system has a plurality of transforming apparatuses 901 to 90N and secure computing apparatuses 91A and 91B. The two secure computing apparatuses 91A and 91B form a secure computing apparatus group 91.
The secure computing apparatus group 91 formed by the secure computing apparatuses 91A and 91B uses data mn (1≦n≦N) retained by the transforming apparatuses 901 to 90N to determine a computation result f(m1, . . . , mN) of a logic circuit function f(x1, . . . , xN) without obtaining data from which the input value mn can be readily reconstructed.
In the following, a procedure therefor will be summarized.
[Step C2-1]
First, the secure computing apparatus 91B performs the following steps (a) to (d) to conceal the logic circuit function f. Then, the secure computing apparatus 91B transmits data Tg associated with the logic circuit function to the secure computing apparatus 91A as concealing data for the logic circuit function f(x1, . . . , xN).
(a) The secure computing apparatus 91B generates fixed-length random numbersWi0,Wi1 for each wire i for the logic circuit function f(x1, . . . , xN) and associates the random numbers with 0 and 1, respectively.
(b) Then, the secure computing apparatus 91B generates a random bit ciε{0, 1}.
(c) Then, the secure computing apparatus 91B associatesWi0,ci,Wi1, ci)with the wire i. In this expression, c=1−c. 
(d) Then, for a logic gate g that receives input wires i and j and provides an output wire k, the secure computing apparatus 91B generates four pieces of labeled dataci,cj:(Wkg(0,0),g(0,0)⊕ck)⊕FWi0(cj)⊕FWj0(ci),ci, cj:(Wkg(0,1),g(0,1)⊕ck)⊕FWi0( cj)⊕FWj1(ci), ci,cj:(Wkg(1,0),g(1,0)⊕ck)⊕FWi1(cj)⊕FWj0( ci), ci, cj:(Wkg(1,1),g(1,1)⊕ck)⊕FWi1( cj)⊕FWj1( ci),and arranges the four pieces of labeled data in a random order to generate data Tg. A set T of the generated data Tg is transmitted to the secure computing apparatus 91A as concealing data for the logic circuit function f(x1, . . . , , xN).
[Step C2-2]
The transforming apparatuses 901 to 90N perform a proxy 1-out-of-2 oblivious transfer protocol with the secure computing apparatuses 91A and 91B to, thereby obtaining dataWib,b⊕ci.
[Step C2-3]
Then, using the data Tg andWib,b⊕cithe secure computing apparatus 91A obtains the output wireWk{circumflex over (b)},{circumflex over (b)}⊕ckof the last-stage logic gate g of the logic circuit function f.
[Step C2-4]
Furthermore, fromWk{circumflex over (b)},{circumflex over (b)}⊕ckthe secure computing apparatus 91A obtains a bit{circumflex over (b)}of the computation result f(m1, . . . , mN).
In step C2-2 in the procedure described above, the proxy 1-out-of-2 oblivious transfer protocol is used. This protocol is an extended version of the 1-out-of-2 oblivious transfer protocol. According to this protocol, on behalf of the transforming apparatuses 901 to 90N, the secure computing apparatus 91A can computeWib,b⊕ciwithout knowing the bit b, which is information about data retained by the transforming apparatuses 901 to 90N.    Non-patent literature 1: A. C. Yao, How to generate and exchange secrets, Proc. of FOCS '86, pp. 162 to 167, IEEE Press, 1986    Non-patent literature 2: S. Even, O. Goldreich and A. Lempel, A randomized protocol for signing contracts, Communications of the ACM, Vol. 28, No. 6, pp. 637 to 647, 1985    Non-patent literature 3: M. Naor, B. Pinkas, and R. Sumner, Privacy preserving auctions and mechanism design, Proc. of ACM EC '99, pp. 129 to 139, ACM Press, 1999